package com.kuang.sort;

/*  手撕快速排序  */


import java.util.Arrays;

/**
 * @author 86184
 */
public class QuickSort {

    //传入一个数组，需要排序的初始位置和结束位置(如果需求不需要这样，在代码里面把start改成0，end改成length-1即可)
    public static int[] quickSort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) {
            return null;
        }
        //返回分区指示器位置
        int zoneIndex = quickPartition(array, start, end);
        if (zoneIndex > start) {
            quickSort(array, start, zoneIndex - 1);
        }
        if (zoneIndex < end) {
            quickSort(array, zoneIndex + 1, end);
        }
        return array;
    }


    //选取基准并且分区
    private static int quickPartition(int[] array, int start, int end) {
        //只有一个元素，无需分区
        if (start == end) {
            return start;
        }
        //随机选取一个基准数，这里随便选一个就行（选第一个也没事）
        int pivot = (int) (start + Math.random() * (end - start + 1));
        //将基准数和最后一位互换
        swapArray(array, pivot, end);
        //基准指示器
        int pivotIndex = start - 1;
        for (int i = start; i <= end; i++) {
            //如果当前元素小于基准数，则基准指示器+1，且看情况交换
            if (array[i] <= array[end]) {
                pivotIndex++;
                if (i > pivotIndex) {
                    swapArray(array, pivotIndex, i);
                }
            }
        }
        return pivotIndex;
    }


    //交换数组内两个元素
    private static void swapArray(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

    }


    public static void main(String[] args) {
        int[] test = {110, 100, 0};
        System.out.println(Arrays.toString(quickSort(test, 0, test.length - 1)));
    }


}
